package com.wc.alorithm_blue_bridge._数学知识.推导.Q2218;

/**
 * @Author congge
 * @Date 2024/1/19 0:29
 * @description 数数
 * https://www.lanqiao.cn/problems/2218/learning/?page=1&first_category_id=1&second_category_id=3
 */
public class Main {
    static int N = 23333333;
    static int[] primes = new int[N];
    static boolean[] isNotPrime = new boolean[N + 1];
    static int idx = 0;

    static void ola() {
        isNotPrime[0] = isNotPrime[1] = true;
        for (int i = 2; i < N; i++) {
            if (!isNotPrime[i]) {
                primes[++idx] = i;
            }

            for (int j = 1; i * primes[j] < N; j++) {
                isNotPrime[i * primes[j]] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    public static void main(String[] args) {
        int st = 2333333;
        int ed = 23333333;
        int ans = 0;
        ola();
        for (int i = st; i <= ed; i++) {
            int num = i;
            if (!isNotPrime[i]) {
                continue;
            }
            int t = 0;
            for (int j = 1; primes[j] * primes[j] <= num; j++) {
                while (num % primes[j] == 0) {
                    num /= primes[j];
                    t++;
                }
                if (!isNotPrime[num]) {
                    t++;
                    num = 1;
                    break;
                }
            }
            if (num > 1) {
                t++;
            }
            if (t == 12) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}
